package com.jack.leetcode.eachProblem07;

/**
 * Created by zhang_j on 2020/7/27
 */
public class 判断子序列 {

    public static void main(String[] args) {
        System.out.println(isSubsequence("abc", "ahbgdc"));
    }

    public static boolean isSubsequence(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        int m = s.length();
        int n = t.length();
        if(m > n){
            return false;
        }

        return isSub(s, 0, t, 0);
    }

    private static boolean isSub(String s, int sBegin, String t, int tBegin){
        if(sBegin == s.length() && tBegin <= t.length()){
            return true;
        }
        if(sBegin >= s.length() || tBegin >= t.length()){
            return false;
        }

        for(int i = tBegin;i < t.length();i++){
            if(t.charAt(i) == s.charAt(sBegin)){
                return isSub(s, sBegin+1, t, i+1);
            }
        }
        return false;
    }
}
